import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution147 {

    public static void main(String args[]){
        Solution147 s = new Solution147();
        ListNode a = new ListNode(5);
        ListNode b = new ListNode(4);
        ListNode c = new ListNode(2);
        ListNode d = new ListNode(3 );
        a.next = b;
        b.next = c;
        c.next = d;
        ListNode ret = s.insertionSortList(a);
        while(ret != null){
            System.out.println(ret.val);
            ret = ret.next;
        }
    }

    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode pre = null;
        ListNode st = head;

        ListNode cur = head.next;
        ListNode next = cur.next;
        st.next = null;

        while(cur != null){
            pre = null;
            st = head;
            while(st != null && cur.val > st.val){
                pre = st;
                st = st.next;
            }

            if(pre == null){
                cur.next = st;
                head = cur;
            }else{
                pre.next = cur;
                cur.next = st;
            }
            cur = next;
            if(cur != null) {
                next = cur.next;
            }
        }
        return head;
    }
}
